package lesson.c3;

import java.util.Arrays;

public class QuickSort {

	public int partition(int []array,int lo,int hi){
        //固定的切分方式
        int key=array[lo];
        while(lo<hi){
            while(array[hi]>=key&&hi>lo){//从后半部分向前扫描
                hi--;
            }
            array[lo]=array[hi];
            while(array[lo]<=key&&hi>lo){//从前半部分向后扫描
                lo++;
            }
            array[hi]=array[lo];
        }
        array[hi]=key;
        return hi;
    }
    
    public void sort(int[] array,int lo ,int hi){
        if(lo>=hi){
            return ;
        }
        int index=partition(array,lo,hi);
        sort(array,lo,index-1);
        sort(array,index+1,hi); 
    }
    
    public void sort2(int[] ary){
    	int temp;
		for (int i = 0; i < ary.length - 1; i++){
			for (int j = i+1; j < ary.length; j++){
				if(ary[i] > ary[j]){
					temp = ary[i];
					ary[i] = ary[j];
					ary[j] = temp;
				}
			}
		}
		
    }

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		QuickSort a = new QuickSort();
		int[] ary = {9,7,8,4,5,3,11,123,21};
		int[] ary2 = {9,7,8,4,5,3,11,123,21};
		a.sort(ary, 0, ary.length - 1);
		a.sort2(ary2);
		System.out.println(Arrays.toString(ary));
		System.out.println(Arrays.toString(ary2));
	}

}
